#define _CRT_SECURE_NO_WARNINGS 1
struct ListNode* BuyNowNode(int x)
{
    struct ListNode* NowNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    NowNode->val = x;
    NowNode->next = NULL;

    return NowNode;
}

void PushBack(struct ListNode** pphead, struct ListNode* Node)
{
    if (*pphead == NULL)
    {
        *pphead = Node;
    }
    else
    {
        struct ListNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = Node;
    }
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;

    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;

    struct ListNode* head = NULL;

    while ((cur1 != NULL) && (cur2 != NULL))
    {
        if (cur1->val > cur2->val)
        {
            struct ListNode* Node = BuyNowNode(cur2->val);
            PushBack(&head, Node);
            cur2 = cur2->next;
            continue;
        }
        if (cur1->val < cur2->val)
        {
            struct ListNode* Node = BuyNowNode(cur1->val);
            PushBack(&head, Node);
            cur1 = cur1->next;
            continue;
        }
        if (cur1->val == cur2->val)
        {
            struct ListNode* Node = BuyNowNode(cur1->val);
            PushBack(&head, Node);
            struct ListNode* Node1 = BuyNowNode(cur2->val);
            PushBack(&head, Node1);
            cur1 = cur1->next;
            cur2 = cur2->next;
            continue;
        }
    }

    if (cur1 == NULL)
    {
        while (cur2)
        {
            struct ListNode* Node = BuyNowNode(cur2->val);
            PushBack(&head, Node);
            cur2 = cur2->next;
        }
    }

    if (cur2 == NULL)
    {
        while (cur1)
        {
            struct ListNode* Node = BuyNowNode(cur1->val);
            PushBack(&head, Node);
            cur1 = cur1->next;
        }
    }

    return head;
}